|
In combinatorial mathematics, a ''k''-ary De Bruijn sequence of order ''n'', named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet ''A'' with size ''k'' for which every possible subsequence of length ''n'' in ''A'' appears as a sequence of consecutive characters exactly once. Each has length ''k''''n''. There are distinct De Bruijn sequences . According to de Bruijn,〔.〕 the existence of De Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie in 1894, whereas the generalization to larger alphabets is originally due to Tanja van Aardenne-Ehrenfest and himself. == History == The earliest known example of a De Bruijn sequence comes from Sanskrit prosody where, since the work of Pingala, each possible three-syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemoic ''yamātārājabhānasalagam'' is used, in which each three-syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagam' which has a short–short–long pattern because of the final consonant. This mnemonic, equivalent to a De Bruijn sequence on binary 3-tuples, is of unknown antiquity, but is at least as old as C. P. Brown's 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by Pāṇini".〔C. P. Brown, 1869, ''Sanskrit Prosody and Numerical Symbols Explained'', (p. 28 )〕〔Subhash Kak, 2000, (Yamātārājabhānasalagāṃ an interesting combinatoric sūtra ), Indian Journal of History of Science, 35.2 (2000), 123–127.〕〔Rachel W. Hall. (Math for poets and drummers ). ''Math Horizons'' 15 (2008) 10–11.〕〔. Reprinted in Wardhaugh, Benjamin, ed. (2012), ''A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing'', Princeton Univ. Press, pp. 139–144.〕 In 1894, A. de Rivière raised the question in an issue of the French problem journal ''L'Intermédiaire des Mathématiciens'', of the existence of a circular arrangement of length which contains all binary sequences of length . The problem was solved, along with the count , by C. Flye Sainte-Marie in the same year.〔 This was largely forgotten, and proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well-known.〔 Karl Popper independently describes these objects in his ''The Logic of Scientific Discovery'' (1934), calling them "shortest random-like sequences". 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「De Bruijn sequence」の詳細全文を読む スポンサード リンク
|